package com.zdp.leetcodeMiddle;

/*
* 题目描述：
* 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
提示：
1 <= nums.length <= 2500
-104 <= nums[i] <= 104
进阶：
你可以设计时间复杂度为 O(n2) 的解决方案吗？
你能将算法的时间复杂度降低到 O(n log(n)) 吗?
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 最长递增子序列_300 {

    private int max = Integer.MIN_VALUE;

    public static void main(String[] args) {
        最长递增子序列_300 demo = new 最长递增子序列_300();
        demo.lengthOfLIS(new int[]{
                1,0,1,3,2,3
        });
        System.out.println(demo.max);
    }
    /*
    * 严格递增： nums[i+1]>nums[i]
    * 要大于 不能是大于等于
    * 可以用深搜写出一个很慢的 超时了淦
    * */
    public int lengthOfLIS(int[] nums) {
        f(nums,0,Integer.MIN_VALUE,0);
        return max;
    }
    public int f(int[] nums,int index,int pre,int count){
        for(int i=index;i<nums.length;i++){
            if(nums[i]>pre){
               max = Math.max(f(nums,i+1,nums[i],count+1),max);
            }
        }
        return count;
    }

    /*
    * 动态规划：
    * 换个思路，通常我们是固定子序列的头部
    * 现在固定子序列的尾部
    * dp[i] 表示 以nums[i]结尾的最长子序列长度
    * 可以得到 dp[i] = max(dp[j])+1  0<=j<i nums[j]<nums[i]
    * 因为 i 在 j的后面，所以dp[i] 可以利用 dp[j]的状态
    * dp[j] 表示 以j结尾的最长子序列长度，如果 nums[i] > nums[j] 那么dp[i]
    * 只要在 dp[j]的基础上 +1 即可。
    * 要找到 最长的那个j
    * */
    public int lengthOfLIS2(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int result = 1;
        for(int i=1;i<nums.length;i++){
            dp[i] = 1;
            for(int j=0;j<i;j++){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            result = Math.max(result,dp[i]);
        }
        return result;
    }

    /*
    * 贪心+二分
    * 贪心： 要得到最长的严格递增子序列，那么我们应该希望子序列每次增加的那个数尽可能的小
    * 所以我们可以创建一个数组d 用来维护各个长度的子序列的最小结尾数
    * d[i] 表示：i长度的子序列 的 末尾元素的最小值
    * 然后分析得到 d[i] 数组 关于 i单调递增， 这样就可以使用二分来进行查找了
    * 遍历 nums[] 中的元素，在遍历的过程中，动态的更新 d 数组
    * 若 nums[i] > d[len] --> d[len+1] = nums[i] len ++;
    * 若 nums[i] < d[len] ---> 则去查找 nums[i] 是否可以用于 d[1~len]中的某个元素
    * 可以更新的条件  d[j] < nums[i] < d[j+1] ---> d[j+1] = nums[i]
    *  这个 d[j] 应该是最靠近 nums[i]的数
    * 为什么要找最靠近的？
    * 因为 d 数组是递增的 若 d[j] < nums[i] 但 d[j+1] < nums[i] 那么d[j+1]就无法更新
    *  1 <= k < j , 1<k+1<j 那么那些小于j的 k 也是无法更新的
    * 如果 d[j] < nums[i] < d[j+1] d[j+1]可以更新 但是因为 d[j] <nums[i]
    * 所以 k+1 也一定小于 nums[i] 是无法更新的，所以找到最靠近 nums[i] 的那个d[j]
    * */
    public int lengthOfLIS3(int[] nums) {
        int[] d = new int[nums.length+1];
        d[1] = nums[0];
        int len = 1;
        // 遍历 Nums数组 更新 d数组和len
        for(int i = 1;i<nums.length;i++){
            if(nums[i]>d[len]){
                d[++len] = nums[i];
            }else{
                // 为什么用二分可以查找到
                /*
                * 因为我们要查找的是最靠近 nums[i]的那个数
                * 如果 d[j]<nums[i] 且 d[j+1]<nums[i]
                * 那么下面的算法得到的一定是j+1
                * 所以不存在什么 d[pos]<nums[i] d[pos+1]<nums[i]
                * */
                //如果 不大于，就在 1~len 中查找最靠近 nums[i]的那个数
                int left = 1;
                int right = len;
                int pos = 0; // 如果找不到，所有所有的数都比nums[i]大,那么就要更新len=1
                while(left<=right){
                    int mid = (left+right) >>1;
                    if( d[mid] < nums[i]){
                        // 小于 nums[i] 记录一下位置，
                        // 然后缩小范围,查找有没有更接近nums[i]的数
                        pos = mid;
                        left = mid+1;
                    }else {
                        // > nums[i]  缩小范围 继续查找
                        right = mid-1;
                    }
                }
                d[++pos] = nums[i];
            }
        }
        return len;
    }
}
